package com.zx._12_算法.剑指offer._2022;

import java.util.Stack;


public class 回文 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 2, 1};    // len = 6, mid = 2, true
        int[] arr1 = {1, 2, 3, 2, 1};    // len = 5, mid = 2, true
        int[] arr2 = {1, 2, 3, 1};        // len = 4, mid = 1, false

        test1(arr);
        test1(arr1);
        test1(arr2);

        test2(arr);
        test2(arr1);
        test2(arr2);

    }

    // 使用栈
    // 2020/05/18	25 - 37 = 12 分钟
    public static void test1(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int len = arr.length;
        int mid = (len - 1) / 2;//中间的索引位置
        boolean flag = len % 2 == 0;//偶数
        boolean bool = true;
        for (int i = 0; i < len; i++) {
            int num = arr[i];

            if (!flag && i == mid) {//奇数中间的值不用管
                continue;
            }

            if (i <= mid) {//入栈
                stack.push(num);
            } else {//出栈
                Integer pop = stack.pop();
                if (num != pop.intValue()) {
                    bool = false;
                    break;
                }
            }
        }
        System.out.println(bool);
    }

    // 二分对比
    // 2020/05/18 54-57 = 3分钟
    public static void test2(int[] arr) {
        int len = arr.length;
        boolean bool = true;
        int left = 0;
        int right = len - 1;
        while (right > left) {
            if (arr[left] != arr[right]) {
                bool = false;
                break;
            }
            left++;
            right--;
        }
        System.out.println(bool);
    }


}
